
null = 'null'


class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    @staticmethod
    def List2ListNode(arr):
        if not arr:
            return None
        head = ListNode(arr[0])
        current = head
        for value in arr[1:]:
            current.next = ListNode(value)
            current = current.next
        return head


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    @staticmethod
    def List2Tree(lst):
        if not lst or lst[0] is None or lst[0] == null:
            return None
        root = TreeNode(lst[0])
        queue = [root]
        i = 1
        while i < len(lst):
            current = queue.pop(0)
            if i < len(lst) and lst[i] is not None and lst[i] != null:
                current.left = TreeNode(lst[i])
                queue.append(current.left)
            i += 1
            if i < len(lst) and lst[i] is not None and lst[i] != null:
                current.right = TreeNode(lst[i])
                queue.append(current.right)
            i += 1
        return root


# todo 经典排序算法
class Sort(object):

    # 快速排序 quick sort
    # 时间复杂度： 通常为 O(nlogn)，与基准元素有关，极端情况下为 O(n^2)
    # 空间复杂度： O(logn)
    # 是否稳定： 否
    # 适用数据集大小： 中等数据集
    def quick_sort(self, arr):  # 快速排序
        if len(arr) <= 1:
            return arr
        pivot = arr[len(arr) // 2]  # 选择中间元素作为基准
        left = [item for item in arr if item < pivot]  # 小于基准的元素
        middle = [item for item in arr if item == pivot]  # 等于基准的元素
        right = [item for item in arr if item > pivot]  # 大于基准的元素
        return self.quick_sort(left) + middle + self.quick_sort(right)

    # 冒泡排序 bubble sort
    # 时间复杂度： O(n^2)
    # 空间复杂度： O(1)
    # 是否稳定： 是
    # 适用数据集大小： 小数据集
    def bubble_sort(self, arr):
        n = len(arr)
        if len(arr) <= 1:
            return arr
        for i in range(n):
            swapped = False  # 用于优化，如果某一轮没有交换，说明数组已排序
            for j in range(n - i):
                if j > 0 and arr[j - 1] > arr[j]:
                    arr[j - 1], arr[j] = arr[j], arr[j - 1]  # 交换相邻元素
                    swapped = True
            if swapped == False:
                break  # 如果没有交换，说明已经排好序，可以提前退出
        return arr

    # 并归排序 merge sort
    # 时间复杂度： O(nlogn)
    # 空间复杂度： O(n)
    # 是否稳定： 是
    # 适用数据集大小： 大数据集
    def merge_sort(self, arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2  # 递归拆分数组
        left = self.merge_sort(arr[:mid])  # 对左半部分排序
        right = self.merge_sort(arr[mid:])  # 对右半部分排序
        return self.merge(left, right)  # 合并两个已经排序的数组

    def merge(self, left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):  # 合并两个有序数组
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result.extend(left[i:])  # 如果左边数组有剩余元素
        result.extend(right[j:])  # 如果右边数组有剩余元素
        return result